import java.util.Arrays;


public class QuickSort {
	public static int[] quickSort(int[] array){
		if (array.length <2)
			return array;
		int ultimo = array.length!=0?array.length-1:0;
		int pivot = array[0];
		int inf = 0;
		int sup = ultimo;
		while(inf<sup){
			while(inf<sup && array[inf]<=pivot)
				inf++;
			while(array[sup]>pivot)
				sup--;
			if(inf<sup)
				intercambiar(array,inf,sup);
		}
		intercambiar(array , 0 , sup);
		int [] less = new int [inf];
		for(int i = 0 ; i< inf ; i++)
			less[i] = array[i];
		int[] greater = new int[array.length - inf];
		for(int i = inf ,j = 0; i<array.length; i++ ,j++)
			greater[j] = array [i];
		
		less = quickSort(less);
		greater = quickSort(greater);
		
		int[]result = new int[less.length + greater.length];
		int i =0;
		for(int a : less)
			result[i++] = a;
		for(int a : greater)
			result[i++] = a;
		return result;
	}

	private static void intercambiar(int[] array, int a, int b) {
		int aux = array[a];
		array[a]= array[b];
		array[b]= aux;
	}
	
	public static void main(String[] args) {
		int[] array = {45,7,34,9, 7,23,65,90,9,12,21,41,108,234,1,1,2};
		array = quickSort (array);
		boolean isLast = false;
		for(int i = 0; i<array.length ;i++){
			isLast = i == array.length -1;
			System.out.print(array[i]);
			if (!isLast)
				System.out.print(" ,");
		}
			
	}
}
